package hot100;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/15 16:56
 */
public class lc322零钱兑换 {
    /*

     */


    public int coinChange(int[] coins, int amount) {
        int recursion = recursion(0, amount, coins, new Integer[coins.length + 1][amount + 1]);
        return recursion >= Integer.MAX_VALUE /2 ? - 1 : recursion;
    }


    public int recursion(int index,int money,int nums[],Integer dp[][]) {
        if (money == 0) {
            return 0;
        }
        if (index == nums.length) {// 不符合条件， 直接返回一个对结果无影响的值
            return Integer.MAX_VALUE / 2;
        }
        if (dp[index][money] != null) {
            return dp[index][money];
        }
        //

        int ans = recursion(index + 1, money, nums, dp);

        if (money - nums[index] >= 0) {
            ans = Math.min(recursion(index + 1, money - nums[index], nums, dp) + 1, ans);
        }


        return dp[index][money] = ans;
    }



    /*
     贪心不正确

     1 6 7  金额 19 就会有问题， 贪心 并不具有正确性
     */
    public int greedy(int nums[],int moeny){
        Arrays.sort(nums);
        int ans = 0;
        for (int i = nums.length - 1; i >=0 ; i--) {
            ans += moeny / nums[i];
            moeny %= nums[i];
        }
        return moeny == 0 ? ans : -1;
    }

}
